#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

#define in read<int>()
#define lin read<ll>()
#define pii pair<int,int>
#define fi first
#define se second
#define FILE(x) freopen(x".in","r",stdin);\
	freopen(x".out","w",stdout);
#define pb push_back

template <typename T>
T read(){
	T x = 0,sgn = 1;char ch = getchar();
	for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;
	for(;isdigit(ch);ch = getchar()) x = (x<<1)+(x<<3)+(ch^48);
	return x*sgn;
}

const int N = 5e4+10;

int mod,n,m,s[N];
ll k;

struct query{ll x;int y,k;}q[N<<1];
bool operator < (query a,query b){return a.x < b.x;}

struct mat{
	int arr[2][2];
	int * operator [] (int x) {return arr[x];}
	const int * operator [](int x) const{return arr[x];}
	mat(){memset(arr,0,sizeof(arr));}
	friend mat operator * (mat a,mat b){
		mat c;
		for(int i = 0;i < 2;i++)
			for(int j = 0;j < 2;j++)
				if(a[i][j])
					for(int k = 0;k < 2;k++)
						c[i][k] = (c[i][k] + 1ll * a[i][j] * b[j][k] % mod) % mod;
		return c;
	}
}val[N<<2],ans,a[N],b[N];

void build(int o = 1,int l = 1,int r = n){if(l == r) return val[o] = a[l],void(); int mid = l + r >> 1; build(o<<1,l,mid); build(o<<1|1,mid+1,r);val[o] = val[o<<1] * val[o<<1|1];}

void upd(int pos,mat v,int o = 1,int l = 1,int r = n){
	if(l == r) return val[o] = v,void(); int mid = l + r >> 1;
	if(pos <= mid) upd(pos,v,o<<1,l,mid);else upd(pos,v,o<<1|1,mid+1,r); val[o] = val[o<<1] * val[o<<1|1];
}

ll o;

void qp(mat x,ll t){for(;t;t >>= 1,x = x * x) if(t & 1) ans = ans*x;}

int main (){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	k = lin; mod = in; n = in; for(int i = 0;i < n;i++) s[i] = in % mod;
	for(int i = 1;i <= n;i++) a[i][1][0] = 1,a[i][0][1] = s[i-1],a[i][1][1] = s[i % n],b[i] = a[i];
	build(); m = in;
	for(int i = 1;i <= m;i++) q[i].x = q[i + m].x = lin,q[i + m].x++,q[i].k = 1,q[i].y = q[i + m].y = in % mod;
	m <<= 1; sort(q+1,q+m+1); ans[0][1] = 1;
	while(m && q[m].x > k) m--;
	for(int i = 1,j = 1;i <= m;i++,i = ++j){
		ll w = (q[i].x - 1) / n; qp(val[1],w - o);o = w;
		while(j < m && (q[j + 1].x - 1) / n == w) j++;
		for(int k = i;k <= j;k++) {
			int ps = (q[k].x - 1) % n + 1; b[ps][q[k].k][1] = q[k].y;
			upd(ps,b[ps]);
		}
		if(w == k / n) break;
		//cerr<<ans[0][0]<<endl;
		ans = ans * val[1]; o = w + 1;
		//	cerr<<ans[0][0]<<"!"<<endl;
		for(int k = i;k <= j;k++){int ps = (q[k].x - 1) % n + 1; upd(ps,b[ps] = a[ps]);}
	}
//	cerr<<ans[0][0]<<endl;
	qp(val[1],k / n - o);
//	cerr<<ans[0][0]<<endl;
	for(int i = 1;i <= k % n;i++) ans = ans * a[i];
//	cerr<<ans[0][0]<<endl;
	printf("%d\n",ans[0][0]);
	return 0;
}

